//
// Created by francklinson on 2021/7/9.
//
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
private:
    const int xMove[4]{1, -1, 0, 0};
    const int yMove[4]{0, 0, 1, -1};
public:
    /**
     * 对于grid2中的每一个岛屿，判断在grid1中对应的每一个位置是不是陆地
     * 需要将一个岛屿的每一个位置都判断过
     * @param grid1
     * @param grid2
     * @return
     */
    int countSubIslands(vector<vector<int>> &grid1, vector<vector<int>> &grid2) {
        unsigned int r = grid1.size();
        unsigned int c = grid1[0].size();
        queue<pair<int, int>> q;
        bool flag = true;
        int subIslandsNumber = 0;
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                if (grid2[i][j] == 1) {
                    // 搜索岛屿 bfs
                    q.emplace(i, j);
                    flag = grid1[i][j];
                    grid2[i][j] = 0;
                    while (!q.empty()) {
                        auto p = q.front();
                        q.pop();
                        // 加入四周的陆地
                        for (int k = 0; k < 4; ++k) {
                            int nr = p.first + xMove[k];
                            int nc = p.second + yMove[k];
                            if (nr >= 0 and nr < r and nc >= 0 and nc < c and grid2[nr][nc] == 1) {
                                q.emplace(nr, nc);
                                grid2[nr][nc] = 0;
                                if (grid1[nr][nc]!=1) flag = false;
                            }
                        }
                    }
                    if (flag) ++subIslandsNumber;
                }
            }
        }
        return subIslandsNumber;
    }

};

int main() {
    vector<vector<int>> grid1{{1, 1, 1, 0, 0},
                              {0, 1, 1, 1, 1},
                              {0, 0, 0, 0, 0},
                              {1, 0, 0, 0, 0},
                              {1, 1, 0, 1, 1}};
    vector<vector<int>> grid2{{1, 1, 1, 0, 0},
                              {0, 0, 1, 1, 1},
                              {0, 1, 0, 0, 0},
                              {1, 0, 1, 1, 0},
                              {0, 1, 0, 1, 0}};
    Solution sol;
    cout << sol.countSubIslands(grid1, grid2) << endl;
    return 0;

}